The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
As Internet Protocol version 4 (IPv4) address space nears exhaustion, stand-alone retail home routers will increasingly use IP version 6 (IPv6). Use of NAT (network address translation) in IPv6 is discouraged. As a result, consensus is growing within the IETF (Internet Engineering Task Force) to use dynamic host configuration protocol version 6 (DHCPv6) prefix delegation in home networks to assign prefixes to subnets instead of NAT, which was used for IPv4. If a home network has more than one router, which is a common deployment scenario, then prefix sub-delegation will be used for IPv6.
One example of a home network with more than one router is a network with (1) a cable modem that includes an embedded router and (2) a retail stand-alone router logically “behind” the embedded router. The embedded router typically does not serve as a wireless access point, while the retail stand-alone router typically does serve as a wireless access point. Because the retail stand-alone router is expected to work without configuration, prefix sub-delegation must be automated.
Use of /64 prefixes is desirable in a home network as this enables the use of Stateless Address Auto Configuration (SLAAC, defined in RFC 48622) for automatically configuring IPv6 addresses of hosts on the subnet. For example, a network Service Provider (SP) delegates a /60 prefix (or any prefix shorter than /64) to an SP-facing home router. The SP-facing router could automatically sub-delegate the prefix through hierarchical sub-delegation. Hierarchical sub-delegation involves an SP-facing router splitting the address based on the number of LAN subnets (to which the SP-facing router is connected) rounded up to the nearest power of 2. “Downstream” routers (or routers that are “behind” the SP-facing router relative to the SP network) can utilize the same mechanism, and all subnets in the home network will be addressed. However, at least two problems arise as a result.
First, address space is not conserved, as not all /64 subnets which are possible from the /60 delegated by the SP are used. Second, hierarchical sub-delegation does not work in arbitrarily routed graph networks because hierarchical sub-delegation “assumes” that the topology of the home network is a tree. The topology of a network refers to the arrangement of the routers in the network. If the topology of a home network is a tree, then there are no cycles in the topology of the home network.